home *** CD-ROM | disk | FTP | other *** search
/ Programmer Plus 2007 / Programmer-Plus-2007.iso / Programming / Compilers / Miracle C Compiler / miricleC compiler.msi / Instal01.cab / _83FEC8EBC1B24155B6D7F3881F5C3E00 < prev    next >
Encoding:
Text File  |  1999-07-23  |  3.8 KB  |  149 lines
  1. /*
  2. Nine puzzle solver
  3.  
  4. A nine-puzzle is a 3x3 with moveable squares 1-8 and one blank
  5. Solve it by 'moving the blank'
  6.  
  7. eg from  top: 1.2           to 312     solution is LDR
  8.          mid: 345              4.5
  9.          bot: 678              678
  10. */
  11.  
  12.  
  13. #include <stdio.h>
  14. #include <ctype.h>
  15. #include <string.h>
  16.  
  17. char  opena[300][10], action[300][20], closed[500][10];
  18.  
  19. void main(), exit(int n);
  20.  
  21. void main()
  22. {
  23.  
  24. char goal[10], initial[10], store[10], current[10];
  25.  
  26. char itop[4], imid[4], ibot[4];
  27. char gtop[4], gmid[4], gbot[4];
  28.  
  29. int open_num, close_num;
  30. int shift, line, got_flag, s_pos, closed_check, s_loop;
  31.  
  32. close_num = open_num = 0;
  33. initial[0] = goal[0] = 0;
  34.  
  35. itop[0] = imid[0] = ibot[0] = 0;
  36. gtop[0] = gmid[0] = gbot[0] = 0;
  37.  
  38. printf("Initial top line   : "); scanf("%s",itop);
  39. printf("Initial middle line: "); scanf("%s",imid);
  40. printf("Initial bottom line: "); scanf("%s",ibot);
  41. printf("\n\n");
  42.  
  43. printf("Goal top line      : "); scanf("%s",gtop);
  44. printf("Goal middle line   : "); scanf("%s",gmid);
  45. printf("Goal bottom line   : "); scanf("%s",gbot);
  46.  
  47. printf("\n\nSearching for solution.\n\n");
  48.  
  49. strcat(initial,itop);
  50. strcat(initial,imid);
  51. strcat(initial,ibot);
  52.  
  53. strcat(goal,gtop);
  54. strcat(goal,gmid);
  55. strcat(goal,gbot);
  56.  
  57. for (line=0; line <300; line++)
  58.      {   action[line][0] = 0;
  59.          opena  [line][0] = 0;   }
  60.  
  61. strcpy(opena[0],initial);
  62.  
  63. for(;;)
  64. {
  65. strcpy(current,opena[0]);
  66. strcpy(closed[close_num++],current);
  67. if (strcmp(goal,current) == 0)
  68.      { printf("Solution found : %s \n",action[0]);
  69.        exit(0); }
  70.  
  71. strcpy(store,current);
  72. s_pos = -1;
  73.  
  74. for(s_loop=0; s_loop<10; s_loop++)
  75. { if(*(current+s_loop) == '.') s_pos = s_loop; }
  76.  
  77. if (s_pos == -1)
  78.      { printf("Illegal input.");
  79.        exit(0); }
  80.  
  81. /* Configuration where empty square goes UP. */
  82.  
  83. if (s_pos > 2) {
  84.  
  85. current[s_pos] = current[s_pos - 3];
  86. *(current + s_pos - 3) = '.';
  87. got_flag = 0;
  88.  
  89. for (closed_check=0; closed_check<=close_num; closed_check++)
  90. { if(strcmp(current,closed[closed_check]) == 0) got_flag=1; }
  91.  
  92. if (got_flag == 0) { strcpy(opena[++open_num],current);
  93.                      strcpy(action[open_num],action[0]);
  94.                      strcat(action[open_num],"U"); } }
  95.  
  96. /* Configuration where empty square goes DOWN. */
  97.  
  98. strcpy(current,store);
  99.  
  100. if (s_pos < 6) {
  101.  
  102. current[s_pos] = current[s_pos+3];
  103. *(current + s_pos + 3) = '.';
  104. got_flag = 0;
  105.  
  106. for (closed_check=0; closed_check<=close_num; closed_check++)
  107. { if(strcmp(current,closed[closed_check]) == 0) got_flag=1; }
  108.  
  109. if(got_flag == 0) { strcpy(opena[++open_num],current);
  110.                     strcpy(action[open_num],action[0]);
  111.                     strcat(action[open_num],"D"); } }
  112.  
  113. /* Configuration where empty square goes LEFT. */
  114.  
  115. strcpy(current,store);
  116.  
  117. if((s_pos!=0) && (s_pos!=3) && (s_pos!=6)) {
  118.  
  119. current[s_pos] = current[s_pos-1];
  120. *(current + s_pos - 1) = '.';
  121. got_flag = 0;
  122.  
  123. for (closed_check=0; closed_check<=close_num; closed_check++)
  124. { if(strcmp(current,closed[closed_check]) == 0) got_flag=1; }
  125.  
  126. if(got_flag==0) { strcpy(opena[++open_num],current);
  127.                   strcpy(action[open_num],action[0]);
  128.                   strcat(action[open_num],"L"); } }
  129.  
  130. /* Configuration where empty square goes RIGHT. */
  131.  
  132. strcpy(current,store);
  133.  
  134. if((s_pos!=2) && (s_pos!=5) && (s_pos!=8)) {
  135. current[s_pos] = current[s_pos+1];
  136. *(current + s_pos + 1) = '.';
  137. got_flag=0;
  138.  
  139. for(closed_check=0; closed_check<=close_num; closed_check++)
  140. { if(strcmp(current,closed[closed_check]) == 0) got_flag=1; }
  141.  
  142. if(got_flag == 0) { strcpy(opena[++open_num],current);
  143.                     strcpy(action[open_num],action[0]);
  144.                     strcat(action[open_num],"R"); } }
  145.  
  146. for(shift=0; shift<open_num; shift++)
  147. { strcpy(opena[shift], opena[shift+1]);
  148.   strcpy(action[shift],action[shift+1]); } } }
  149.